package primary;

import Utils.SortUtils;

/**
 * 希尔排序(将数组根据固定长度 h分成多个独立的小数组进行排序，再通过改变 h的值再排序，直到 h=1)
 * @author xiaolu
 * @version 1.0
 * @date 2020/6/1 14:59
 */
public class Shell {

    public static void sort(Comparable[] a){

        int N = a.length;
        int h = 1;
        while (h < N/3){
            h = 3 * h + 1;
        }
        while (h >= 1){
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && SortUtils.less(a[j],a[j-h]) ; j-=h) {
                    SortUtils.exch(a, j, j-h);
                }
            }
            h = h / 3;
        }
    }

    public static void main(String[] args) {

        // 测试排序算法
        Integer[] a = {4, 23, 6, 78, 1, 54, 231, 9, 12};
        // Integer[] a = {1, 5, 6, 4, 343, 234};
        sort(a);
        assert SortUtils.isSorted(a);
        SortUtils.show(a);
    }
}
